/*
 * @lc app=leetcode.cn id=22 lang=golang
 * @lcpr version=30118
 *
 * [22] 括号生成
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func generateParenthesis(n int) []string {
	if n == 0 {
		return []string{}
	} else if n == 1 {
		return []string{"()"}
	} else {
		res := []string{}
		dfs("", n, n, &res)
		return res
	}
}

func dfs(s string, left int, right int, res *[]string) {
	if right < left || left < 0 || right < 0 {
		return
	}
	if left == 0 && right == 0 {
		*res = append(*res, s)
	}
	dfs(s+"(", left-1, right, res)
	dfs(s+")", left, right-1, res)
	return
}

// @lc code=end

/*
// @lcpr case=start
// 3\n
// @lcpr case=end

// @lcpr case=start
// 1\n
// @lcpr case=end

*/

